% Copyright (c) 2010 Vincent Renaudineau, Jérémie DECOCK

% This document is provided under the terms of the "Creative Commons BY-SA" license.
% For more details, read "legalcode.html" enclosed file or "http://creativecommons.org/licenses/by-sa/2.0/fr/" web page.

\documentclass{beamer}
\usepackage[utf8]{inputenc}
\usepackage[frenchb]{babel}
\usepackage{hyperref}
\usepackage{subfigure}
%\usepackage[pdftex]{graphicx}
%\usepackage{natbib}
\usepackage{listings}
%\usepackage{algorithmic}
\usepackage{calc}

\lstset{
    basicstyle=\small,                                % print whole listing small
    keywordstyle=\color{black}\bfseries\underbar,     % underlined bold black keywords
    identifierstyle=,                                 % nothing happens
    commentstyle=\color{white},                       % white comments
    stringstyle=\ttfamily,                            % typewriter type for strings
    showstringspaces=false                            % no special string spaces
}


\hypersetup{
	pdftoolbar=true,                                          % show Acrobat’s toolbar ?
	pdfmenubar=true,                                          % show Acrobat’s menu ?
	pdffitwindow=true,                                        % page fit to window when opened
	pdftitle={Search for novelty},                                % title
	pdfauthor={Jérémie DECOCK},                                                                               % author
	pdfsubject={Search for novelty},  % subject of the document
	pdfnewwindow=true,                                                                                        % links in new window
	pdfkeywords={novelty, algorithmes évolutionnistes},                               % list of keywords
	colorlinks=true,                                          % false: boxed links; true: colored links
	linkcolor=black,                                          % color of internal links
	citecolor=black,                                          % color of links to bibliography
	filecolor=black,                                          % color of file links
	urlcolor=black                                            % color of external links
}

\mode<presentation> {
    \usetheme{Frankfurt}
}

\usepackage{verbatim}
%\usetheme{Singapore}

%\setbeamertemplate{footline}
%{%
%    \leavevmode%
%    \hbox{\begin{beamercolorbox}[wd=.5\paperwidth,ht=2.5ex,dp=1.125ex,leftskip=.3cm plus1fill,rightskip=.3cm]{author in head/foot}%
%    \usebeamerfont{author in head/foot}\insertshortauthor
%    \end{beamercolorbox}%
%    \begin{beamercolorbox}[wd=.5\paperwidth,ht=2.5ex,dp=1.125ex,leftskip=.3cm,rightskip=.3cm plus1fil]{title in head/foot}%
%    \usebeamerfont{title in head/foot}\insertshorttitle\hfill \insertpagenumber{} / \inserttotalframenumber
%    \end{beamercolorbox}}%
%    \vskip0pt%
%}

\title{Exploiting Open-Endedness to Solve Problems Through the Search for Novelty ~~~~~~~~~~~~~~~~~~ [Lehman and Stanley, 2008]}
\author{Vincent \bsc{Renaudineau} ~~~ Jérémie \bsc{Decock}}
\institute{UPMC}
\date{24 mars 2010}

\begin{document}

\begin{frame}
\titlepage
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Plan}
%\tableofcontents
\tableofcontents[sectionstyle=show/show,subsectionstyle=hide/hide/hide]
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}
\begin{frame}
\begin{center}
{\LARGE Introduction}
\end{center}
\end{frame}

\subsection{Introduction}

\begin{frame}{Introduction}
    Exploiting Open-Endedness to Solve Problems Through the Search for Novelty [Lehman and Stanley, 2008]
    \begin{enumerate}
         \item Une approche originale pour contourner le piège des optimums locaux dans les algorithmes évolutionnistes
         \item Évaluation basée sur la \og{}nouveauté\fg{} du comportement plut\^{o}t que sur la fitness
         \item Archive des comportements innovants et comparaison d'un nouvel individu à cette archive pour l'évaluer
    \end{enumerate}
    \bigskip
	$\Rightarrow$ Permet de créer des animats au comportement plus complexe
	$\Rightarrow$ Contourne la difficulté liée au choix de la fonction de fitness
\end{frame}


\begin{frame}
\frametitle{Contexte historique}
Novelty search
\begin{itemize}
    \item Les fondements biologiques% : théorie sur l'origine de la complexité et l'innovation ne proviennent pas d'une pression sélective mais d'une marche aléatoire (biologie)
    %\item la complexité et l'innovation ne proviennent pas d'une pression sélective mais d'une marche aléatoire (biologie)
    \begin{itemize}
        \item Miconi
        \item Lynch
    \end{itemize}
    \item Les algorithmes évolutionnistes ouverts (sans contraintes) % flexibles
    \begin{itemize}
        \item Bedau et al.
        \item Tierra, Polyworld, Geb
        \item Standish
    \end{itemize}
\end{itemize}
~\\
NEAT%Évolution de réseaux de neurones
\begin{itemize}
    \item Kenneth, Stanley et al. $[$Stanley and Miikkulainen, 2002$]$
\end{itemize}
~\\
Behavioral diversity [Mouret and Doncieux, 2009]
\begin{itemize}
    \item MOEA [Mouret and Doncieux, 2008]
    %\item ...
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Les avancées récentes}
Réseaux de neurones évolutionistes [Risi and al., 2009]
\begin{itemize}
    \item Utiliser la recherche de nouveauté pour améliorer les performances de réseaux de neurones adaptatifs
\end{itemize}
~\\
Novelty-based Multiobjectivization [Mouret, 2009]
\begin{enumerate}
     \item La nouveauté seule ne converge pas vers l'optimal m\^{e}me s'il est à coté.
     \item La fonction d'évaluation d'un individu utilise les deux critères de nouveauté et de fitness pour l'évaluer.
     \item Pour cela il utilise la dominance de Pareto.
\end{enumerate}
\bigskip
 $\Rightarrow$ L'espace est exploré un peu moins vite, mais les solutions sont de meilleure qualité.
\end{frame}


%\begin{frame}{Introduction}
%	\begin{itemize}
%		\item Decock et Renaudineau, 2010
%			\begin{enumerate}
%				 \item Pareto permet d'éliminer les individus dominés, mais comment comparer les individus incomparables ?
%				 \item Utilisation de différentes fonctions d'agrégation des scores de fitness et de nouveauté. 
%			\end{enumerate}
%	\end{itemize}
%\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Matériels, méthodes et résultats}
\begin{frame}
\begin{center}
{\LARGE Matériels, méthodes et résultats}
\end{center}
\end{frame}


\begin{frame}
\frametitle{Expériences}
Nos travaux :
\begin{itemize}
    \item prise en main de la méthode
    \item prise en main de la plate-forme \emph{NoveltySearch C++}
    \item vérifier les expériences de l'article (fitness et novelty)
    \item explorer la méthode avec d'autres expériences
    \item proposer une nouvelle méthode basée sur l'agrégation de la fitness et de la nouveauté
\end{itemize}
\end{frame}


\subsection{Travail préliminaire}

\begin{frame}{Plan - \secname}
\tableofcontents[sectionstyle=hide/hide,subsectionstyle=show/shaded/hide ]
\end{frame}


\begin{frame}
\frametitle{Prise en main de la méthode}
\begin{itemize}
    \item Exploiting open-endedness to solve problems through the search for novelty [Lehman and Stanley, 2008].
    \item Novelty-based multiobjectivization [Mouret, 2009].
    \item Incremental evolution of animats' behaviors as a multi-objective optimization [Mouret and Doncieux, 2008].
    \item Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity [Mouret and Doncieux, 2009].
    \item How novelty search escapes the deceptive trap of learning to learn [Risi and al., 2009].
    %\item Real-time neuroevolution in the NERO video game [Stanley, Bryant and Miikkulainen, 2005].
    \item Evolving neural networks through augmenting topologies [Stanley and Miikkulainen, 2002].
    \item Competitive coevolution through evolutionary complexification [Stanley and Miikkulainen, 2004].
\end{itemize}
\end{frame}


\begin{frame}{Expériences}
\begin{itemize}
    \item Évolution d'un réseau de neurones pour contrôler un robot (10 entrées, 2 sorties)
    \item Aller du point rouge au point vert dans un labyrinthe
    \item Le labyrinthe comporte des pièges (extremums locaux)
    \item On compare les performances entre recherche par fitness et par nouveauté
\end{itemize}
\begin{figure}
    \centering
    \subfigure{\includegraphics[width=.30\linewidth,height=.30\linewidth]{images/hard_maze}}~~~
    \subfigure{\includegraphics[width=.30\linewidth,height=.30\linewidth]{images/robot}}~~~
    \subfigure{\includegraphics[width=.30\linewidth,height=.30\linewidth]{images/medium_maze}}
\end{figure}
\end{frame}


\begin{frame}{Expériences}
\begin{block}{Critères}
    \begin{enumerate}
        \item Fitness = distance au point d'arrivé à un temps t
        \item Nouveauté = densité de la position à un temps t
    \end{enumerate}
\end{block}
\end{frame}


\begin{frame}
\frametitle{NoveltySearch C++}
Prise en main de la plate-forme \emph{NoveltySearch C++}
\begin{itemize}
    \item Écriture d'outils pour visualiser et étudier le fonctionnement de la plate-forme
    \begin{itemize}
        \item MapViewer : affiche les labyrinthes (en C++/Qt) avec les résultats
        \item MazeViewer : affiche les labyrinthes (en Python/PySFML)
        \item NNViewer : affiche les réseaux de neurones (en C++/Qt)
    \end{itemize}
    \item Modification de la plate-forme
    \begin{itemize}
        \item Agrégation fitness et nouveauté
        \item Tracé des individus dans le labyrinthe
        \item De nombreuses autres petites modifications (hooks, ...)
    \end{itemize}
    \item Écriture de scripts pour visualiser les résultats
    \begin{itemize}
        \item Plusieurs scripts (octave, python, ruby, shell)
        \item Des vidéos montrant la progression de l'évolution
    \end{itemize}
\end{itemize}
\end{frame}


\begin{frame}{Outils et scripts}
%\begin{figure}
%    \centering
%    \subfigure{\includegraphics[width=.40\linewidth,height=.30\linewidth]{images/hard_nov}}~~~
%    \subfigure{\includegraphics[width=.40\linewidth,height=.30\linewidth]{images/nnv1}}
%\end{figure}
\begin{center}
    \includegraphics[width=.65\linewidth]{images/hard_nov}
\end{center}
\end{frame}


\begin{frame}{Outils et scripts}
\begin{center}
    \includegraphics[width=.75\linewidth]{images/nnv1}
\end{center}
\end{frame}


\begin{frame}{Outils et scripts}
\begin{center}
    \includegraphics[width=.95\linewidth]{images/traces}
\end{center}
\end{frame}


\begin{frame}{Outils et scripts}
\begin{figure}
    \centering
    \subfigure{\includegraphics[width=.30\linewidth,height=.30\linewidth]{images/snail2_nov}}~~~
    \subfigure{\includegraphics[width=.30\linewidth,height=.30\linewidth]{images/novelty}}~~~
    \subfigure{\includegraphics[width=.30\linewidth,height=.30\linewidth]{images/runresults}}
\end{figure}
\end{frame}


\subsection{Expériences initiales}

\begin{frame}{Plan - \secname}
\tableofcontents[sectionstyle=hide/hide,subsectionstyle=show/shaded/hide ]
\end{frame}


\begin{frame}
\frametitle{Vérification des expériences}
Vérification des expériences de l'article
\begin{itemize}
    \item Fitness (moyenne sur 5 run)
    \item Novelty (moyenne sur 5 run)
\end{itemize}
\begin{figure}
    \centering
    \subfigure{\includegraphics[width=.40\linewidth,height=.30\linewidth]{images/hard_nov}}~~~
    \subfigure{\includegraphics[width=.40\linewidth,height=.30\linewidth]{images/medium_nov}}
\end{figure}
\end{frame}


\begin{frame}{Résultats}
Medium maze (moyenne sur 5 run)
\begin{center}
    \includegraphics[width=.95\linewidth]{images/medium_bestfitness_means}
\end{center}
\end{frame}


\begin{frame}{Résultats}
Hard maze (moyenne sur 5 run)
\begin{center}
    \includegraphics[width=.95\linewidth]{images/hard_bestfitness_means_1}
\end{center}
\end{frame}


\begin{frame}{Résultats}
Résultats comparables à ceux de Lehman et Stanley
\begin{itemize}
    \item La fitness est piégée par la hardmap et ne parvient pas souvent à l'optimal
    \item La recherche de nouveauté converge toujours sur les deux cartes
    \item La recherche de nouveauté converge beaucoup plus vite qu'avec la fitness (quand elle y parvient)
\end{itemize}
~\\
Quelques différences
\begin{itemize}
    \item Nos expériences convergent plus rapidement
    \item La recherche par fitness obtient des résultats légèrement supérieurs
\end{itemize}
~\\
Nous utilisons pourtant les mêmes paramètres.
\end{frame}


\subsection{Expériences supplémentaires}

\begin{frame}{Plan - \secname}
\tableofcontents[sectionstyle=hide/hide,subsectionstyle=show/shaded/hide ]
\end{frame}


\begin{frame}
\frametitle{Expériences supplémentaires}
Exploration de la méthode avec d'autres expériences
\begin{figure}
    \centering
    \subfigure{\includegraphics[width=.40\linewidth,height=.30\linewidth]{images/easy_nov}}~~~
    \subfigure{\includegraphics[width=.40\linewidth,height=.30\linewidth]{images/easysnail_nov}}
    ~\\
    \subfigure{\includegraphics[width=.40\linewidth,height=.30\linewidth]{images/snail}}~~~
    \subfigure{\includegraphics[width=.40\linewidth,height=.30\linewidth]{images/snail_nov}}
\end{figure}
\end{frame}


\begin{frame}{Outils et scripts}
\begin{figure}
    \centering
    \subfigure{\includegraphics[width=.40\linewidth,height=.30\linewidth]{images/snail_nov}}~~~
    ~\\
    \subfigure{\includegraphics[width=.30\linewidth,height=.30\linewidth]{images/snail2_nov}}~~~
    \subfigure{\includegraphics[width=.30\linewidth,height=.30\linewidth]{images/snail2_fit}}
\end{figure}
\end{frame}


\subsection{Extension de la méthode}

\begin{frame}{Plan - \secname}
\tableofcontents[sectionstyle=hide/hide,subsectionstyle=show/shaded/hide ]
\end{frame}


\begin{frame}{Fitness et nouveauté}
	Nous avons testé plusieurs fonctions d'agrégation des deux critères :
	\begin{block}{La combinaison linéaire}
		$$\alpha*fitness + (1 - \alpha)*novelty$$
	\end{block}
	\begin{block}{La combinaison probabiliste}
		$$fitness * novelty$$
	\end{block}
	\begin{block}{La combinaison linéaire en fonction du temps}
		$$\alpha(t)*fitness + (1 - \alpha(t))*novelty$$
		\begin{enumerate}
			\item exponentielle	$\alpha(t) = \exp^{t - T_{max}}$
			\item sinusoïdale $\alpha(t) = 0.5+\sigma*sin(\frac{t}{\tau})$
		\end{enumerate}
	\end{block}
\end{frame}


\begin{frame}{Résultats}
La combinaison linéaire (moyenne sur 5 run)
\begin{center}
    \includegraphics[width=.95\linewidth]{images/hard_bestfitness_means}
\end{center}
\end{frame}


%\begin{frame}{Résultats}
%La combinaison probabiliste
%La combinaison linéaire en fonction du temps
%IMAGES ...
%\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Discussion et conclusion}
\begin{frame}
\begin{center}
{\LARGE Discussion et conclusion}
\end{center}
\end{frame}


\subsection{Conclusion}

\begin{frame}
\frametitle{Conclusion}
Résultats
\begin{itemize}
    \item Les résultats sont conformes aux attentes
    \item La recherche par nouveauté contourne les limites de méthodes traditionnelles
\end{itemize}
~\\
Retombées
\begin{itemize}
    \item La recherche par nouveauté est une approche originale et très prometteuse pour améliorer les performances des algorithmes évolutionnistes
    \item C'est une approche nouvelle
    \item Des travaux récents ont montrés qu'elle améliore significativement les performances les réseaux de neurones adaptatifs [Risi and al., 2009]
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Discussion}
\begin{itemize}
    \item La recherche par nouveauté supprime un point délicat : la recherche d'une fonction de fitness efficace (bootstrap, etc.)...
    \item Mais il faut toutefois choisir une bonne mesure de distance dans l'espace de recherche (point final, chemin, ...)
\end{itemize}
~\\
\begin{itemize}
    \item Nous avons également montré qu'une approche moins radicale que celle proposée par Lehman et Stanley offre de meilleurs résultats
    \item Toutefois l'agrégation n'est pas une solution idéale (solutions ignorées, ...)
    \item La multiobjectivisation basée sur l'algorithme MOEA offre de meilleures performances [Mouret, 2009]
\end{itemize}
~\\
\begin{itemize}
    \item Il serait également souhaitable d'augmenter le nombre de \og{}runs\fg{} pour obtenir des moyennes plus fiables
\end{itemize}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[allowframebreaks]
\frametitle{Bibliographie}
\begin{itemize}
    \item $[$Lehman and Stanley, 2008$]$
    J.~Lehman and K.O. Stanley.
    Exploiting open-endedness to solve problems through the search for
    novelty.
    In  Proceedings of the Eleventh International Conference on
    Artificial Life (ALIFE XI) Cambridge MA: MIT Press, volume~54, 2008.

    \item $[$Mouret, 2009$]$
    J.B. Mouret.
    Novelty-based multiobjectivization.
    In  Proceedings of IROS Workshop” Exploring New Horizons in the
    Evolutionary Design of Robots, 2009.

    \item $[$Mouret and Doncieux, 2008$]$
    J.B. Mouret and S.~Doncieux.
    Incremental evolution of animats' behaviors as a multi-objective
    optimization.
    Lecture Notes in Computer Science, 5040:210--219, 2008.

    \item $[$Mouret and Doncieux, 2009$]$
    J.B. Mouret and S.~Doncieux.
    Overcoming the bootstrap problem in evolutionary robotics using
    behavioral diversity.
    In  Proceedings of the Congress on Evolutionary Computation 2009
    (to appear), 2009.

    \item $[$Risi and al., 2009$]$
    S.~Risi, S.D. Vanderbleek, C.E. Hughes, and K.O. Stanley.
    How novelty search escapes the deceptive trap of learning to learn.
    In  Proceedings of the 11th Annual conference on Genetic and
    evolutionary computation, pages 153--160. ACM, 2009.

    \item $[$Stanley, Bryant and Miikkulainen, 2005$]$
    K.O. Stanley, B.D. Bryant, and R.~Miikkulainen.
    Real-time neuroevolution in the NERO video game.
    IEEE Transactions on Evolutionary Computation, 9(6):653--668,
    2005.

    \item $[$Stanley and Miikkulainen, 2002$]$
    K.O. Stanley and R.~Miikkulainen.
    Evolving neural networks through augmenting topologies.
    Evolutionary Computation, 10(2):99--127, 2002.

    \item $[$Stanley and Miikkulainen, 2004$]$
    K.O. Stanley and R.~Miikkulainen.
    Competitive coevolution through evolutionary complexification.
    Journal of Artificial Intelligence Research, 21(1):63--100,
    2004.

%    \item $[$9$]$
%    S.~Koos, J.B. Mouret, and S.~Doncieux.
%    Automatic system identification based on coevolution of models and
%    tests.
%    In  IEEE Congress on Evolutionary Computation, volume 2009,
%    2009.
\end{itemize}
\end{frame}

\begin{frame}
\begin{center}
    \href{http://creativecommons.org/licenses/by-sa/2.0/fr/}{\includegraphics[width=.40\linewidth]{images/cc_by_sa}}
    %\\[3em]
    %\textbf{Illustrations}\\\medskip
    %\href{http://commons.wikimedia.org/wiki/User:Nojhan}{Johann "nojhan" Dréo} \raisebox{-0.5\height+0.3em}{\href{http://creativecommons.org/licenses/by-sa/2.0/fr/}{\includegraphics[height=1em]{images/cc_by_sa_small}}}
\end{center}
\end{frame}

\end{document}
